#include <iostream>
#include "gtest/gtest.h"
#include "utils/Utils.h"

#include "graph/Graph.h"
#include "graph/GraphAlgorithm.h"

using namespace std;


int main(int argc, char *argv[]) {
	testing::InitGoogleTest(&argc, argv);
	return RUN_ALL_TESTS();
}

TEST(GraphTest, ArrGraphTest) {
	ArrGraph ag(7);
	ag.AddEdge(0, 1);
	ag.AddEdge(0, 2);
	ag.AddEdge(0, 3);
	ag.AddEdge(1, 4);
	ag.AddEdge(1, 5);
	ag.AddEdge(2, 4);
	ag.AddEdge(3, 5);
	ag.AddEdge(4, 6);
	ag.AddEdge(5, 6);
	ag.Show();

	vector<int> ret = ag.Adj(1);
	Utils::PrintVector(ret);

	ret = GraphAlgorithm::BFS(&ag, 0);
	Utils::PrintVector(ret);

	ret = GraphAlgorithm::DFS(&ag, 0);
	Utils::PrintVector(ret);
}

TEST(GraphTest, ListGraphTest) {
	ListGraph lg(7);
	lg.AddEdge(0, 1);
	lg.AddEdge(0, 2);
	lg.AddEdge(0, 3);
	lg.AddEdge(1, 4);
	lg.AddEdge(1, 5);
	lg.AddEdge(2, 4);
	lg.AddEdge(3, 5);
	lg.AddEdge(4, 6);
	lg.AddEdge(5, 6);
	lg.Show();

	vector<int> ret = lg.Adj(1);
	Utils::PrintVector(ret);

	ret = GraphAlgorithm::BFS(&lg, 0);
	Utils::PrintVector(ret);

	ret = GraphAlgorithm::DFS(&lg, 0);
	Utils::PrintVector(ret);
}

TEST(GraphTest, ListGraphMSTPrim) {
	ListGraph lg(8);
	lg.AddEdge(0, 2, 26);
	lg.AddEdge(0, 4, 38);
	lg.AddEdge(0, 6, 58);
	lg.AddEdge(0, 7, 16);
	lg.AddEdge(1, 2, 36);
	lg.AddEdge(1, 3, 29);
	lg.AddEdge(1, 5, 32);
	lg.AddEdge(1, 7, 19);
	lg.AddEdge(2, 3, 17);
	lg.AddEdge(2, 6, 40);
	lg.AddEdge(2, 7, 34);
	lg.AddEdge(3, 6, 52);
	lg.AddEdge(4, 5, 35);
	lg.AddEdge(4, 6, 93);
	lg.AddEdge(4, 7, 37);
	lg.AddEdge(5, 7, 28);
	lg.Show();

	GraphAlgorithm::MST_Prim(&lg);
}

TEST(GraphTest, ListGraphMSTKsuskal) {
	ListGraph lg(8);
	lg.AddEdge(0, 2, 26);
	lg.AddEdge(0, 4, 38);
	lg.AddEdge(0, 6, 58);
	lg.AddEdge(0, 7, 16);
	lg.AddEdge(1, 2, 36);
	lg.AddEdge(1, 3, 29);
	lg.AddEdge(1, 5, 32);
	lg.AddEdge(1, 7, 19);
	lg.AddEdge(2, 3, 17);
	lg.AddEdge(2, 6, 40);
	lg.AddEdge(2, 7, 34);
	lg.AddEdge(3, 6, 52);
	lg.AddEdge(4, 5, 35);
	lg.AddEdge(4, 6, 93);
	lg.AddEdge(4, 7, 37);
	lg.AddEdge(5, 7, 28);
	lg.Show();

	GraphAlgorithm::MST_Ksuskal(&lg);
}